Minimal Adaptive Routing on the Mesh with Bounded Queue Size
Identifieur interne : 001C61 ( Main/Exploration ); précédent : 001C60; suivant : 001C62Minimal Adaptive Routing on the Mesh with Bounded Queue Size
Auteurs : Donald D. Chinn [États-Unis] ; Tom Leighton ; Martin Tompa [États-Unis]Source :
- Journal of Parallel and Distributed Computing [ 0743-7315 ] ; 1996.
English descriptors
- Teeft :
- Active packet, Active packets, Adaptive, Algorithm, Chinn, Computer science, Current node, Destination, Destination addresses, Destination column, Dimension order, Dimension order algorithm, Dimension order part, Entire algorithm, Horizontal balancing, Horizontal phase, Horizontal subphase, Inqueue, Inqueue policy, Iteration, Leighton, Lemma, Lower bounds, Mesh, Minimal adaptive, More packets, Node, Nodes west, Nonminimal, Other packets, Outlink, Outlinks, Outqueue, Outqueue policy, Packet, Parallel algorithms, Permutation, Preferred directions, Queue, Queue size, Same node, Same time, Source addresses, Subphase, Subphases, Substage, Tiling, Tompa, Torus, Vertical phase, Worst case.
Abstract
Abstract: An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing packets around “hot spots.” Minimal adaptive routing algorithms have the additional advantage that the path each packet takes is a shortest one. For a large class of minimal adaptive routing algorithms, we present an Ω(n2/k2) bound on the worst case time to route a static permutation of packets on ann×nmesh or torus with nodes that can hold up tok≥ 1 packets each. This is the first nontrivial lower bound on adaptive routing algorithms. The argument extends to more general routing problems, such as theh–hrouting problem. It also extends to a large class of dimension order routing algorithms, yielding an Ω(n2/k) time bound. To complement these lower bounds, we present two upper bounds. One is anO(n2/k+n) time dimension order routing algorithm that matches the lower bound. The other is the first instance of a minimal adaptive routing algorithm that achievesO(n) time with constant sized queues per node. We point out why the latter algorithm is outside the model of our lower bounds.
Url:
DOI: 10.1006/jpdc.1996.0052
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001836
- to stream Istex, to step Curation: 001836
- to stream Istex, to step Checkpoint: 000A40
- to stream Main, to step Merge: 001D29
- to stream Main, to step Curation: 001C61
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Minimal Adaptive Routing on the Mesh with Bounded Queue Size</title><author><name sortKey="Chinn, Donald D" sort="Chinn, Donald D" uniqKey="Chinn D" first="Donald D." last="Chinn">Donald D. Chinn</name></author><author><name sortKey="Leighton, Tom" sort="Leighton, Tom" uniqKey="Leighton T" first="Tom" last="Leighton">Tom Leighton</name></author><author><name sortKey="Tompa, Martin" sort="Tompa, Martin" uniqKey="Tompa M" first="Martin" last="Tompa">Martin Tompa</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:A04FF93D6DF6779A1C320BE60604F4DCFF441D6B</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1006/jpdc.1996.0052</idno><idno type="url">https://api.istex.fr/ark:/67375/6H6-21VFLHXZ-Z/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">001836</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001836</idno><idno type="wicri:Area/Istex/Curation">001836</idno><idno type="wicri:Area/Istex/Checkpoint">000A40</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000A40</idno><idno type="wicri:doubleKey">0743-7315:1996:Chinn D:minimal:adaptive:routing</idno><idno type="wicri:Area/Main/Merge">001D29</idno><idno type="wicri:Area/Main/Curation">001C61</idno><idno type="wicri:Area/Main/Exploration">001C61</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Minimal Adaptive Routing on the Mesh with Bounded Queue Size</title><author><name sortKey="Chinn, Donald D" sort="Chinn, Donald D" uniqKey="Chinn D" first="Donald D." last="Chinn">Donald D. Chinn</name><affiliation wicri:level="4"><orgName type="university">Université de Washington</orgName><country>États-Unis</country><placeName><settlement type="city">Seattle</settlement><region type="state">Washington (État)</region></placeName></affiliation></author><author><name sortKey="Leighton, Tom" sort="Leighton, Tom" uniqKey="Leighton T" first="Tom" last="Leighton">Tom Leighton</name><affiliation><wicri:noCountry code="subField">02139</wicri:noCountry></affiliation></author><author><name sortKey="Tompa, Martin" sort="Tompa, Martin" uniqKey="Tompa M" first="Martin" last="Tompa">Martin Tompa</name><affiliation wicri:level="4"><orgName type="university">Université de Washington</orgName><country>États-Unis</country><placeName><settlement type="city">Seattle</settlement><region type="state">Washington (État)</region></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">Journal of Parallel and Distributed Computing</title><title level="j" type="abbrev">YJPDC</title><idno type="ISSN">0743-7315</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1996">1996</date><biblScope unit="volume">34</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="154">154</biblScope><biblScope unit="page" to="170">170</biblScope></imprint><idno type="ISSN">0743-7315</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0743-7315</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Active packet</term><term>Active packets</term><term>Adaptive</term><term>Algorithm</term><term>Chinn</term><term>Computer science</term><term>Current node</term><term>Destination</term><term>Destination addresses</term><term>Destination column</term><term>Dimension order</term><term>Dimension order algorithm</term><term>Dimension order part</term><term>Entire algorithm</term><term>Horizontal balancing</term><term>Horizontal phase</term><term>Horizontal subphase</term><term>Inqueue</term><term>Inqueue policy</term><term>Iteration</term><term>Leighton</term><term>Lemma</term><term>Lower bounds</term><term>Mesh</term><term>Minimal adaptive</term><term>More packets</term><term>Node</term><term>Nodes west</term><term>Nonminimal</term><term>Other packets</term><term>Outlink</term><term>Outlinks</term><term>Outqueue</term><term>Outqueue policy</term><term>Packet</term><term>Parallel algorithms</term><term>Permutation</term><term>Preferred directions</term><term>Queue</term><term>Queue size</term><term>Same node</term><term>Same time</term><term>Source addresses</term><term>Subphase</term><term>Subphases</term><term>Substage</term><term>Tiling</term><term>Tompa</term><term>Torus</term><term>Vertical phase</term><term>Worst case</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing packets around “hot spots.” Minimal adaptive routing algorithms have the additional advantage that the path each packet takes is a shortest one. For a large class of minimal adaptive routing algorithms, we present an Ω(n2/k2) bound on the worst case time to route a static permutation of packets on ann×nmesh or torus with nodes that can hold up tok≥ 1 packets each. This is the first nontrivial lower bound on adaptive routing algorithms. The argument extends to more general routing problems, such as theh–hrouting problem. It also extends to a large class of dimension order routing algorithms, yielding an Ω(n2/k) time bound. To complement these lower bounds, we present two upper bounds. One is anO(n2/k+n) time dimension order routing algorithm that matches the lower bound. The other is the first instance of a minimal adaptive routing algorithm that achievesO(n) time with constant sized queues per node. We point out why the latter algorithm is outside the model of our lower bounds.</div></front></TEI><affiliations><list><country><li>États-Unis</li></country><region><li>Washington (État)</li></region><settlement><li>Seattle</li></settlement><orgName><li>Université de Washington</li></orgName></list><tree><noCountry><name sortKey="Leighton, Tom" sort="Leighton, Tom" uniqKey="Leighton T" first="Tom" last="Leighton">Tom Leighton</name></noCountry><country name="États-Unis"><region name="Washington (État)"><name sortKey="Chinn, Donald D" sort="Chinn, Donald D" uniqKey="Chinn D" first="Donald D." last="Chinn">Donald D. Chinn</name></region><name sortKey="Tompa, Martin" sort="Tompa, Martin" uniqKey="Tompa M" first="Martin" last="Tompa">Martin Tompa</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/H2N2V1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001C61 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001C61 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= H2N2V1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:A04FF93D6DF6779A1C320BE60604F4DCFF441D6B
|texte= Minimal Adaptive Routing on the Mesh with Bounded Queue Size
}}
| This area was generated with Dilib version V0.6.33. |  |